1. Field of the Invention (Technical Field)
The present invention relates to methods, software, and apparatuses for improving data channels suffering from intersymbol interference (ISI).
2. Description of Related Art
Note that the following discussion refers to a number of publications by author(s) and year of publication, and that due to recent publication dates certain publications are not to be considered as prior art vis-à-vis the present invention. Discussion of such publications herein is given for more complete background and is not to be construed as an admission that such publications are prior art for patentability determination purposes.
It is well known that maximum likelihood sequence detection (MLSD) is an optimal equalization technique for intersymbol interference (ISI) channels in the sense that it minimizes the sequence error probability for equally likely input data sequences. G. D. Forney. Jr., “Maximum-likelihood sequence estimation of digital sequences in the presence of intersymbol interference,” IEEE Trans. Inform. Theory, vol. 18, pp. 363-378, May 1972. However, the number of states in the Viterbi algorithm (VA) while implementing MLSD grows exponentially with ISI length and the number of bits per constellation point. Other equalization techniques such as linear and decision feedback equalizers have also been thoroughly investigated in the literature. Although they provide low complexity approaches, their bit error rate (BER) performance may significantly fall short of MLSD's performance. J. G. Proakis, Digital Communications, 4th ed. New York: McGraw-Hill, 2000.
In order to design reduced complexity MLSD for long ISI channels, many researchers have focused on channel shortening before using MLSD. For this purpose, both linear and decision feedback equalizers have been used to reduce ISI length before applying the MLSD algorithm. D. D. Falconer and F. R. Magee Jr., “Adaptive channel memory truncation for maximum likelihood sequence estimation” Bell Syst. Tech. J., vol. 52, pp. 1541-1562, November 1973; W. U. Lee and F. S. Hill, “A maximum-likelihood sequence estimator with decision-feedback equalizer,” IEEE Trans. Commun., vol. 25, pp. 971-979, September 1977; and N. Al-Dhahir and J. M. Cioffi, “Efficiently computed reduced-parameter input-aided MMSE equalizers for ML detection: A unified approach,” IEEE Trans. Inform. Theory, vol. 42, pp. 903-915, May 1996. However, perfect channel shortening is difficult and the BER performance degrades due to residual filter errors. Other complexity reduction approaches include a reduction in the number of surviving paths in VA, F. L. Vermeulen and M. E. Hellman, “Reduced-state Viterbi decoders for channels with intersymbol interference,” Proc. IEEE ICC'1974, Minneapolis, 1974, reduced state sequence estimators for large signal constellation sizes, M. V. Eyuboglu, and S. U. Qureshi, “Reduced-state sequence estimation with set partitioning and decision feedback,” IEEE Trans. Commun., vol. 36, pp. 13-20, January 1988, and delayed decision feedback sequence estimators for long ISI channels, A. Duel-Hallen, and C. Heegard, “Delayed decision-feedback sequence estimation,” IEEE Trans. Commun., vol. 37, pp. 428-436, May 1989. However, none of the above sub-optimum techniques achieves close to MLSD performance without a significant increase in implementation complexity. Hence, for long ISI channels and large symbol alphabets, complexity and BER performance have been a matter of trade-off.
Recently, the inventors in H. Vikalo, B. Hassibi, and U. Mitra, “Sphere-constrained ML detection for frequency-selective channels,” IEEE Trans. Commun., vol. 54, pp. 1179-1183, July 2006, extended the sphere decoder (SD) algorithm of U. Fincke and M. Pohst, “Improved methods for calculating vectors of short length in a lattice, including a complexity analysis,” Math Comput., vol. 44, pp. 463-471, April 1985; R. Kannan, “Improved algorithms for integer programming and related lattice problems,” Proc. ACM Symp. Theory of Comput.', 1983; and E. Viterbo and J. Boutros, “A universal lattice code decoder for fading channels,” IEEE Trans. Inform. Theory, vol. 45, pp. 1639-1642, July 1999, for frequency selective channels. The resulting algorithm is a hybrid of VA and SD. From the results on SD described in J. Jalden and B. Ottersten, “On the complexity of sphere decoding in digital communications,” IEEE Trans. Signal Processing, vol. 53, pp. 1474-1484, April 2005, it can be seen that the complexity of this algorithm is exponential in block length, and so this algorithm is suitable only for short data lengths. In S. Ohno and G. B. Giannakis, “ML sequence estimation for long ISI channels with controllable complexity,” Proc. IEEE ICC'2004, Paris, 2004, a method called distributed zero padding (D-ZP) is shown to achieve a BER performance comparable to maximum likelihood (ML) detection for binary signaling. However, regular insertion of zeros during transmission compromises its effective data rate. A fast MLSD method that provides significantly low complexity at high signal-to-noise ratio (SNR) over vector ISI channels has also been recently described in J. Luo, “Fast maximum likelihood sequence detection over vector intersymbol interference channels,” Proc. IEEE ICASSP'2007, Honolulu, 2007.
Existing methods of dealing with ISI do not offer near-optimal performance without significant complexity. The present invention, a list based data detection method, apparatus, and software for long intersymbol interference channels, is able to guarantee a specified level of near-optimal performance with low complexity. The invention first extracts bit reliabilities using a low complexity equalizer and then uses these reliabilities to generate lists of possible data vectors before making final bit decisions. The invention can ensure a specific bit error rate performance with respect to a maximum likelihood sequence detector.
List based techniques have also been considered by other researchers in various contexts. For example, a list-type generalization of the VA is proposed in T. Hashimoto, “A list-type reduced-constraint generalization of the Viterbi algorithm,” IEEE Trans. Inform. Theory, vol. 33, pp. 866-876, November 1987, where a number of survivors is selected from lists of candidates at each decoding step of the VA. In C. Kuhn and J. Hagenauer, “8-PSK turbo equalization with the list-sequential (LISS) algorithm,” Proc. IEEE ISIT'2004, Chicago, 2004, a list-sequential equalizer, based on a modified stack algorithm, is discussed. This algorithm operates in the turbo equalization framework, and uses the information fed back from the channel decoder. However, the present invention focuses on an equalization algorithm without involving any channel decoder, and includes the following additional contributions. The invention uses a Chase-type algorithm, D. Chase, “A class of algorithms for decoding block codes with channel measurement information,” IEEE Trans. Inform. Theory, vol. 18, pp. 170-182, January 1972, for equalization of ISI channels. In earlier work, the Chase algorithm has been used to explore the soft decision decoding of block and turbo product codes. R. M. Pyndiah, “Near-optimum decoding of product codes: block turbo codes,” IEEE Trans. Commun., vol. 46, pp. 1003-1010, August 1998; and X. Wu, H. R. Sadjadpour, and Z. Tian, “A new adaptive two-stage maximum-likelihood decoding algorithm for linear block codes,” IEEE Trans. Commun., vol. 53, pp. 909-913, June 2005. It has also been used for multisymbol differential detection, W. Xiaofu and S. Songgeng, “Low complexity multisymbol differential detection of MDPSK over flat correlated Rayleigh fading channels,” IEE Electronics Lett., vol. 34, pp. 2008-2009, October 1998, detection over multiple input multiple output channels, D. Waters and J. R. Barry, “The Chase family of detection algorithms for multiple-input multiple-output channels,” Proc. IEEE GLOBECOM'2004, Dallas, 2004, and for multiuser detection in spread spectrum systems, Z. Qin and K. C. Teh, “Iterative reduced-complexity multiuser detection based on Chase decoding for synchronous turbo-coded CDMA system,” IEEE J. Select. Areas Commun., vol. 24, pp. 200-208, January 2006. A direct application of the Chase algorithm, however, generates many test patterns, thereby increasing the complexity significantly. The invention uses the Chase method with a windowed technique resulting in significantly lower complexity. The invention also employs a threshold based list generation approach for implementing Chase. Finally, near-ML performance is obtained with significantly low complexity.